It is well known that there is only one finite field of any given order, but that there are many different representations. When an extension field is built by adjoining a root of an irreducible polynomial to the ground field, the choice of irreducible affects the representation of the extension field. In general if Fqm is the finite field, where q is a prime and Fq is the ground field over which it is defined, the elements of the finite field can be represented in a number of ways depending on the choice of basis. In order to interoperate, cryptographic systems employing finite fields often need to establish a common representation. In addition to the choice of irreducible polynomial, finite fields can also be represented by either polynomial or normal basis. A polynomial basis represents elements of Fqm as linear combinations of the powers of a generator element x: {x0, x1, . . . xm−1}. A normal basis representation represents elements as linear combination of successive q-th powers of the generator element x: {xq5, xq1, . . . xqm−1}. Each basis has its own advantages, and cryptographic implementations may prefer one or the other, or indeed specific types of irreducible polynomials, such as trinomials or pentanomials.
To support secure communication between devices using different representations, basis conversion, which changes the representation used by one party into that used by another party is generally required.
Basis conversion often entails the evaluation of a polynomial expression at a given finite field element. If an element a, when represented as a polynomial, is given as a(x)=Σaixi mod f(x), where f(x) is an irreducible, in one basis, then the conversion of the element a into a new representation using another irreducible polynomial requires that a be evaluated at r, where r is a root of the new irreducible polynomial in the field represented by f(x), then a(r) is the element a in the new representation. Any of the conjugates of r (the other roots of the new irreducible) will also induce equivalent, but different representations.
There is a need for an efficient method for evaluating these polynomials, for application to basis conversion.